\chapter{Вопрос №9}

Рекррентные соотношения - основные определения, методы решения, не использующие производящие функции.

\section{Основные определения}

Пусть имеется последовательность чисел $$ a_0, a_1, a_2, ... $$ такая, что для любого числа $n \ge m > 0$ справедливо соотношение $$ a_{n+m} = f\left(a_{n+m-1},a_{n+m-2},a_{n+m-3},...,a_n\right) $$. Тогда вся последовательность называется рекуррентной, а выражение называется рекуррентным выражением для числовой последовательности порядка $m$.

Линейным рекуррентным соотношением $m$-ого порядка называется рекуррентное соотношение вида:
\begin{equation}
	a_{n+m} = b_1\left(n\right)a_{n+m-1} + b_2\left(n\right)a_{n+m-2} + ... + b_m\left(n\right)a_m + u\left(n\right)
\end{equation}
Если $u\left(n\right) \equiv 0$, то рекуррентное соотношение называется однородным.

Если $b_i\left(n\right) \equiv const$, то соотношение называется соотношением с постоянными коэффициентами.

\section{Методы решения}

В случае простых рекуррентных соотношений решение можно записать сходу, например:
\[
	a_{n+1} = ba_n
\]
решением будет следующая замкнутая формула $$ a_n = a_0 b^n $$. Положим, что все решения таких рекуррентных соотношений являются полиномами, напрмер рассмотрим:
\[
	a_{n+2} = b_1 a_{n+1} + b_2 a_n
\]
ищем решение в виде $a_n = r^n$, тогда подставив получим уравнение:
\[
	r^{n+2} = b_1 r^{n+1} + b_2 r^{n} \Leftrightarrow r^2 - b_1 r - b_2 = 0
\]
Такое уравнение называется характеристическим, оно имеет 3 различных варианта решения:
\[
	\begin{split}
		& r_1 \not = r_2 \in \mathbb{R}\\
		& r_1,r_2 \in \mathbb{C}\\
		& r_1 = r_2 \in \mathbb{R}
	\end{split}
\]
И тут есть аналогия между линейными дифференциальными уравнениями и линейными рекуррентными уравнениями. Рассмотрим как в зависимости от значений корней характеристического уравнения ищется решение.
\begin{enumerate}
\item Случай различных корней: $$ a_n = c_1 r_1^n + c_2 r_2^n $$. Константны $c_1$ и $c_2$ находятся из начальных условий на рекуррентную последовательность.

\item Случай кратных корней: $$ a_n = c_1 nr^n + c_2r^n $$. Константны опять же ищутся из начальных условий.
\end{enumerate}

\section{Пример - числа Фибоначчи}

Рассмотрим рекуррентное соотношение:
\begin{equation}
	F_{n+2} = F_{n+1} + F_n
\end{equation}
при начальных условиях:
\[
	F_0 = 0; F_1 = 1
\]
это рекуррентное соотношение для чисел Фибоначчи. Характеристическое уравнение для данной рекуррентной последовательности:
\begin{equation}
	r^2 - r -1 = 0
\end{equation}
а корни опеделяются формулой:
\[
	r_{1,2} = \frac{1\pm \sqrt{5}}{2}
\]
константны найдем из начальных условий:
\[
	\begin{split}
		&0 = c_1 + c_2\\
		&1 = c_1 \frac{1+\sqrt{5}}{2} + c_2 \frac{1-\sqrt{5}}{2}
	\end{split}
\]
откуда находим:
\[
	c_{1,2} = \pm \frac{1}{\sqrt{5}}
\]
Решение:
\begin{equation}
	F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n
\end{equation}
